package leetcode.median;

/**
 * ClassName: $494_FindTargetSumWays
 * Description:
 * date: 2022-01-25 10:45
 *
 * @author liyifan
 */
public class $494_FindTargetSumWays {

    int count = 0;

    public int findTargetSumWays(int[] nums, int target) {
        recur(nums, target, 0, 0);
        return count;
    }

    public void recur(int[] nums, int target, int index, int sum) {
        if(index == nums.length) {
            if(sum == target){
                count++;
            }
        } else {
            recur(nums, target, index + 1, sum + nums[index]);
            recur(nums, target, index + 1, sum - nums[index]);
        }
    }

    public int findTargetSumWaysDP(int[] nums, int target) {
        int sum = 0;
        for (int i = 0;i < nums.length;i++) {
            sum += nums[i];
        }
        int negative = (sum - target) / 2;
        if ((sum - target) % 2 != 0 || negative < 0) {
            return 0;
        }
        int[] dp = new int[negative + 1];
        dp[0] = 1;

        for (int i = 1;i <= nums.length;i++) {
            int temp = nums[i - 1];
            for (int j = negative;j >= temp;j--) {
                dp[j] = dp[j] + dp[j - temp];
            }
        }
        return dp[negative];
    }
}
